package leetcode.code1019;

import java.util.HashMap;
import java.util.Iterator;
import java.util.Map;
import java.util.Stack;

import leetcode.helper.tree.ListNode;

public class Solution2 {
	public int[] nextLargerNodes(ListNode head) {
		ListNode node = head;
		node = head;
		int p = 0;
		Stack<int[]> stack = new Stack<>();
		Map<Integer, Integer> map = new HashMap<>();
		while (node != null) {
			int val = node.val;
			while (!stack.isEmpty() && val > stack.peek()[0]) {
				int[] cur = stack.pop();
				map.put(cur[1], val);
			}
			stack.add(new int[] { val, p });
			node = node.next;
			p++;
		}
		int[] ans = new int[p];
		for (Map.Entry<Integer, Integer> entry : map.entrySet()) {
			ans[entry.getKey()] = entry.getValue();
		}
		return ans;
	}
}
